package cn.z2huo.leetcode.problem.NO_0001;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
 * <p>示例:
 * <p>给定 nums = [2, 7, 11, 15], target = 9
 * <p>因为 nums[0] + nums[1] = 2 + 7 = 9
 * <p>所以返回 [0, 1]
 *
 * @author z2huo
 */
class Solution {

    public static void main(String[] args) {

    }

    /**
     * <p>通过两个嵌套循环，找出数组中两数之和为 target 的两个元素的下标
     *
     * @param nums   给定的整数数组
     * @param target 目标值
     * @return int[]    数组 nums 中和为 target 的两个值的下标数组
     */
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    /**
     * <p>两次循环遍历
     * <p>第一次循环将数组中的元素及下标添加到 HashMap 中
     * <p>第二次遍历数组，从 HashMap 中找出与当前遍历元素相加等于 target 的元素
     *
     * @param nums   给定的整数数组
     * @param target 目标值
     * @return int[]    数组 nums 中和为 target 的两个值的下标数组
     */
    public int[] twoSumHash(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (map.containsKey(temp) && map.get(temp) != i) {
                return new int[]{i, map.get(temp)};
            }
        }
        return null;
    }

    /**
     * <p>一次循环遍历
     * <p>在循环过程中在不断向 HashMap 中添加数组元素的同时在 HashMap 中寻找与当前遍历元素相加等于 target 的元素
     * <p>与两次遍历哈希表不同，当遍历到满足条件的元素时，该元素应该放到结果数组的后一位。
     *
     * @param nums   给定的整数数组
     * @param target 目标值
     * @return int[]    数组 nums 中和为 target 的两个值的下标数组
     */
    public int[] twoSumOnceHash(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (map.containsKey(temp) && map.get(temp) != i) {
                return new int[]{map.get(temp), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}
